public class MaxProfit3 {
    // 买卖股票的最佳时机3
    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // f[i][j]表示第i天交易次数为j次，并且为买入状态时候的最大利润
        int[][] f = new int[len][3];
        // g[i][j]表示第i天交易次数为j次，并且为卖出状态时候的最大利润
        int[][] g = new int[len][3];
        f[0][0] = f[0][1] = f[0][2] = -prices[0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if (j-1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }
        return Math.max(Math.max(g[len-1][0], g[len-1][1]), g[len-1][2]);
    }

    // 空间优化
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        // f[i][j]表示第i天交易次数为j次，并且为买入状态时候的最大利润
        int[] f = new int[3];
        // g[i][j]表示第i天交易次数为j次，并且为卖出状态时候的最大利润
        int[] g = new int[3];
        f[0] = f[1] = f[2] = -prices[0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < 3; j++) {
                f[j] = Math.max(f[j], g[j] - prices[i]);
                if (j-1 >= 0) {
                    g[j] = Math.max(g[j], f[j-1] + prices[i]);
                }
            }
        }
        return Math.max(Math.max(g[0], g[1]), g[2]);
    }

    public static void main(String[] args) {
        int[] prices = {3,3,5,0,0,3,1,4};
        System.out.println(new MaxProfit3().maxProfit(prices));
    }
}
